精通C语言？短短20行经典C语言代码很多人看不明白，你来试一下吧
江南一散人 2020-05-02 08:56:02
引言
昨天发了一个文章《简历上写精通C语言？有道C语言的题来做一下吧》，引来很多童鞋围观。很多童鞋表示不太明白，于是就有了这篇文章，详细解释下这个题目的来龙去脉。
题目如下图所示（对原题目做了少许改动）：
#includeint test (int count) { int i = 0; int n = (count + 7) /8 ; // 假设count > 0 switch(count % 8) { case 0: do{ i++; case 7: i++; case 6: i++; case 5: i++; case 4: i++; case 3: i++; case 2: i++; case 1: i++; }while(--n > 0); } return i; } int main() { printf("%d\n", test (20)); return 0; }
如果你是第一次看到的话，不妨试一下，看你能得出正确答案吗？
其实，这个题目还是源自大师之手，我只是做了少许修改。先来聊一下这段历史渊源吧。
注：为了尽量解释清楚，篇幅有点长，请耐心读完，相信你会有收获的！
历史渊源
1983年11月，一位叫Tom Duff的大牛在编写串口通信程序时，发现使用一般的写法时，性能总是不能让人满意。后来，这位老兄凭借深厚的编程功底和精湛的C语言技巧，利用C语言中switch语句的一个鲜为人知的特性，发明如了下图所示的经典代码：
typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
void send(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = (count + 7) /8 ; // 假设count > 0
switch(count % 8)
{
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n > 0);
}
}
结果，引来无数吃瓜群众膜拜。在此之前，还没有人发现并利用过C语言的这个特性，于是他便以自己的名字命名这段代码，叫做Duff's Device，一般译为“达夫机器”。
先来看一下大牛的风采吧：
Tom Duff
下面来讲解一下这段代码吧。
Duff's Device - 达夫机器
当时Duff的需求是把一段起始地址为from，长度为count的数据，写入到一个内存映射的I/O（Memory Mapped I/O ）寄存器to中。
最简单的实现
需求很简单，对吧？很容易想到直接用for或者while循环就可以解决了，如所示：
void send(uint8_t* to, uint8_t* from, uintl6_t count)
{
do{
*to = *from++; // 假设count > 0
}while(--count > 0);
}
代码清晰简洁，很直观，对吧？
Duff却对此很不满意，因为他觉得这种写法虽然简单，但太过低效，无法接受。
那么，为什么如此简单的代码，却说它性能低下呢？其实主要有两个问题：
① 无用指令太多。
② 热点路径上分支指令太多，无法充分发挥CPU的ILP（Instruction-Level Parallelism）技术。
我们来分析一下。
1 无用指令太多
所谓无用指令，是指不直接对所期望的结果产生影响的指令。
对于这段代码，我们期望的结果就是把数据都拷贝到I/O寄存器to中。那么对于这个期望的结果来说，真正有用的代码，其实只有中间那一行赋值操作：
*to = *from++;
而每次迭代过程中的while (--count > 0)产生的条件判断指令，以及每次迭代结束后的跳转指令，对结果来说都是无用指令。降低了CPU流水线停顿引起的性能开销。
上面最简单的实现中，每次循环迭代只拷贝一个字节数据。这就意味着，有多少个字节的数据，就需要执行多少次跳转和条件判断，以及--count的操作。
我们看一下send()的汇编代码：
44: do{
45: *to = *from++; // 假设count > 0
00401308 mov eax,dword ptr [ebp+8]
0040130B mov ecx,dword ptr [ebp+0Ch]
0040130E mov dl,byte ptr [ecx]
00401310 mov byte ptr [eax],dl
00401312 mov eax,dword ptr [ebp+0Ch]
00401315 add eax,1
00401318 mov dword ptr [ebp+0Ch],eax
46: }while(--count > 0);
0040131B mov cx,word ptr [ebp+10h]
0040131F sub cx,1
00401323 mov word ptr [ebp+10h],cx
00401327 mov edx,dword ptr [ebp+10h]
0040132A and edx,0FFFFh
00401330 test edx,edx
00401332 jg send2+18h (00401308)
47: }
有些童鞋对汇编不太熟悉，我简单讲解一下：
- 第08~18，对应C语言的*to = *from++；
- 第1B~32，对应C语言的while (--count > 0)；
所以，第08~18属于热点路径，也就是主循环体，属于有效指令，第1B~32对于期望的数据结果来说就是无用指令。
我们看到，热点路径中，无用指令数占了整个热点路径指令数的一半，其开销也占到整个函数的50%！
2 热点路径上分支指令太多，无法充分发挥CPU的ILP技术优势
现代CPU为了提高指令执行的速度和吞吐率，提升系统性能，不仅一直致力于提升CPU的主频，还实现了多种ILP(Instruction-Level Parallelism 指令级并行)技术，如超流水线、超标量、乱序执行、推测执行、分支预测等。
一个设计合理的程序，往往能够充分利用CPU的这些ILP机制，以使性能达到最优。
但是，在代码热点路径上，分支指令太多，导致程序运行中产生大量指令流水线停顿，无法充分发挥ILP的技术优势，从而导致巨大的性能优势。
注：由于ILP涉及到很底层的CPU硬件知识，很多童鞋可能不熟悉，要讲清楚的话，需要花费大量篇幅。而且，很多童鞋可能也不会有耐心去看，所以这里就暂时先不展开了。
但是，了解一些ILP的知识，对于进行系统性的性能优化大有裨益。而且，要想真正理解并掌握如perf这样的性能测量工具，ILP更是必须要掌握的知识。
因此，后续我会更新专题文章进行讲解这方面的知识，有兴趣的童鞋可以关注一下。
现在，我们知道上面那个简单实现性能低下的原因了，那么如何去优化它呢？这就需要用到循环展开的优化手段了。
循环展开
所谓循环展开，是通过增加每次迭代内数据操作的次数，来减小迭代次数，甚至彻底消除循环迭代的一种优化手段。
循环展开，有以下优点：
- 有效减少因循环引起的分支指令。我们前面提过了，这种指令，实际上是对结果不产生影响的无用指令。减少这些指令，就可以减少这些指令本身执行所需的开销，从而提升整体性能。
- 由于减少了分支指令，可以减少由此引起的CPU指令流水线的停顿，更加有效的利用指令级并行（ILP）技术。
循环展开是一个很常用的性能优化手段。几乎所有的现代编译器，在编译代码时，都会尝试进行循环展开优化。
有童鞋可能会好奇，循环展开到底能提升多少性能呢？我们还是用数据说话，看一个实例吧。
实例 - 循环展开对性能的影响
测试代码：test2() 和 test3()
int test2(unsigned n,unsigned *m)
{
clock_t start = clock();
unsigned sum=0;
n-=7;
for(unsigned i=0;i<n;i++)
(sum)++;
*m=sum;
return (clock()-start);
}
int test3(int n,unsigned *m)
{
clock_t start = clock();
unsigned sum=0;
n-=7;
for(unsigned i=0;i<n;i+=8) // 要避免陷入死循环，所以n-=7;
{
sum++;
sum++;
sum++;
sum++;
sum++;
sum++;
sum++;
sum++;
}
*m=sum;
return (clock()-start);
}
test2()和test3()做的事情一样，唯一的区别是：
- test2()每次循环迭代执行一次k++
- test3()每次循环执行8次k++，但是循环的次数比loop1.c少了8倍
测试结果test3()花费的时间要小。
25690 4294967288 22759 4294967288
第一次优化尝试
了解了循环展开对性能提升的好处之后，我们就可以对上面的简单实现进行第一次优化尝试了。
我们先尝试把每次循环内拷贝字节的个数，由1个提高到到8个，这样就可以把迭代次数降低8倍。
我们先假设，send()函数的参数count总是8的倍数，那么上面的代码就可以修改为：
void send(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = count / 8 ; // 假设count > 0，且是8的倍数
do{ *to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
}while(--n > 0);
}
第一次优化 - count是8的倍数
上面的代码很好理解，就是把原来迭代里的操作复制了8次，然后把迭代次数降低到了8倍。
但是，我们前面做了一个假设，就是count是8的倍数。那如果不是8的整数倍呢，比如20？那我们可能会想到这样的实现：
void send(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = count / 8 ; // 假设count > 0
do{ *to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
}while(--n > 0);
n = count % 8 ;
while(--n > 0)
*to = *from++;
}
第一次优化，且 count > 0
其实，到了这里，相比原始的实现来说，性能已经能提升了不少了。但是，Duff仍然不满意，他看着第二个while循环非常不爽，尽管对整体性能已经没有太大影响了。
也许这就是大牛与我等普通码农的区别，大牛总是追求极致，总是可以在看似不可能的时候，再往前走一步。
C语言switch-case的一些特性
Duff注意到C语言中switch-case语句的一些特性：
- case语句后面的break语句不是必须的。
- 在switch语句内，case标号可以出现在任意的子语句之前，甚至运行出现在if、for、while等语句内。
于是，Duff便利用switch-case的特性，用来处理第一个while循环之后仍然剩余的count % 8个字节的数据。于是便有了这样的代码：
typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
void send0(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = (count + 7) /8 ; // 假设count > 0
switch(count % 8)
{
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n > 0);
}
}
Duff's Device
稍微解释下这段代码：
我们假设count = 20，那么：
n = (count + 7) / 8 = 27 / 8 = 3
count % 8 = 4
所以：
- switch语句会落入case 4的标签内，然后依次执行了case 4、3、2、1四条语句。自此之后，其实就跟switch-case语句再也没有关系了。
- while语句判断--n > 0，条件成立，于是跳转到case 0进入循环体执行，于是依次执行case 0、7、6、5、4、3、2、1一共8条语句。此时n = 2.
- 再次进入while语句处判断--n >0，条件成立，再次跳转到case 0处进入循环体执行。此时n = 1。
- 此时，while语句处判断--n >0，条件失败，退出循环，函数结束。
好了，到这里，大家应该理解Duff's Device了吧？还是不清楚的话，可以尝试单步跟踪一下，就会很清晰了。
揭晓答案
理解了Duff's Device之后，文章开头的那个题目就很好理解了，现在揭晓答案：
再看一下源码：
#include <stdio.h>
int test (int count)
{
int i = 0;
int n = (count + 7) /8 ; // 假设count > 0
switch(count % 8)
{
case 0: do{ i++;
case 7: i++;
case 6: i++;
case 5: i++;
case 4: i++;
case 3: i++;
case 2: i++;
case 1: i++;
}while(--n > 0);
}
return i;
}
int main()
{
printf("%d\n", test (20));
getchar();
return 0;
}
答案是：20
结语
随着硬件的性能越来越好，容量越来越大，导致很多童鞋觉得，现在去纠结诸如Cache、ILP、循环展开等优化手段没有太大的现实意义。
但是，当系统遇到性能瓶颈而又找不到解决思路时，往往在这些平时被绝大多数人忽略的地方，能收到意想不到的收获！而且，一个设计精良的系统，往往设计之初就要充分考虑到这些因素，只有这样才能把硬件的性能充分挖掘出来。
限于篇幅原因，对Cache、ILP技术无法展开介绍，后续我会更新一系列文章，详细介绍这些技术细节。感兴趣的童鞋，不妨右上角关注一下！谢谢！
最后，友情提示：Duff's Device虽然很精妙，但是对于绝大多数童鞋来说，理解起来还是相对比较困难的。因此，产品代码中，不建议使用。否则，轻则被其他童鞋群殴，重则直接被拿来祭天！
全部代码：
#include <stdio.h>
#include <malloc.h>
#include <ctime>
int test (int count)
{
int i = 0;
int n = (count + 7) /8 ; // 假设count > 0
// 要达到i++执行count次，如果count<8時，如果不+7，n=0，会执行8次i++，而不是7次
switch(count % 8)
{
case 0: do{ i++;
case 7: i++;
case 6: i++;
case 5: i++;
case 4: i++;
case 3: i++;
case 2: i++;
case 1: i++;
}while(--n > 0);
}
return i;
}
typedef unsigned char uint8_t;
typedef unsigned short int uint16_t;
void send1(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = (count + 7) /8 ; // 假设count > 0
switch(count % 8)
{
case 0: do{ *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
}while(--n > 0);
}
}
void send2(uint8_t* to, uint8_t* from, uint16_t count)
{
do{
*to = *from++; // 假设count > 0
}while(--count > 0);
}
void send3(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = count / 8 ; // 假设count > 0，且是8的倍数
do{ *to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
}while(--n > 0);
}
void send(uint8_t* to, uint8_t* from, uint16_t count)
{
uint16_t n = count / 8 ; // 假设count > 0
do{ *to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
*to = *from++;
}while(--n > 0);
n = count % 8 ;
while(--n > 0)
*to = *from++;
}
int test2(unsigned n,unsigned *m)
{
clock_t start = clock();
unsigned sum=0;
n-=7;
for(unsigned i=0;i<n;i++)
(sum)++;
*m=sum;
return (clock()-start);
}
int test3(int n,unsigned *m)
{
clock_t start = clock();
unsigned sum=0;
n-=7;
for(unsigned i=0;i<n;i+=8) // 要避免陷入死循环，所以n-=7;
{
sum++;
sum++;
sum++;
sum++;
sum++;
sum++;
sum++;
sum++;
}
*m=sum;
return (clock()-start);
}
int main()
{
printf("%d\n", test (20));
uint16_t count = 8;
uint8_t* to = (uint8_t*)malloc(sizeof(uint8_t)*2);
to[1] = '\0';
uint8_t from[9] = "abcdefgh";
send1(to,from,count);
printf("%s\n",to); // h
send2(to,from,count);
printf("%s\n",to); // h
send3(to,from,count);
printf("%s\n",to); // h
unsigned n = -1; // 4294967295 0xffffffff
unsigned sum = 0;
// 在debug模式下运行，如果在release下运行，时间接近0秒
printf("%d\n",test2(n,&sum));
printf("%u\n",sum);
sum = 0;
printf("%d\n",test3(n,&sum));
printf("%u\n",sum);
getchar();
return 0;
}
/*
20
h
h
h
24875
4294967288
21745
4294967288
*/